package com.dyz.leetcode._01_array;

public class _31_nextPermutation {
    //规律题目
    public void nextPermutation(int[] nums) {
        //从右边开始，找左边小于相邻右边的值，尽量找靠右的较小值，
        int i = nums.length-2;
        while(i>=0 && nums[i]>=nums[i+1]){
            i--;
        }

        //如果找到较小值i>=0;未找到较小值i=-1
        if(i>=0){
            //尽量在较小值找到较大值
            int j=nums.length-1;
            while(j>=0 && nums[i]>=nums[j]){
                j--;
            }

            //较大值与较小值交换
            swap(nums, i, j);
        }

        //反转较小数后面的所有的元素
        reverse(nums, i+1);


    }
    private void swap(int[] nums, int i, int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    private void reverse(int[] nums, int i){
        int start = i;
        int end = nums.length-1;
        while(start< end){
            swap(nums, start, end);
            start++;
            end--;
        }
    }
}
